/*
 * @lc app=leetcode.cn id=54 lang=cpp
 *
 * [54] 螺旋矩阵
 *
 * https://leetcode-cn.com/problems/spiral-matrix/description/
 *
 * algorithms
 * Medium (48.48%)
 * Likes:    1014
 * Dislikes: 0
 * Total Accepted:    234.3K
 * Total Submissions: 483.2K
 * Testcase Example:  '[[1,2,3],[4,5,6],[7,8,9]]'
 *
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * m == matrix.length
 * n == matrix[i].length
 * 1 
 * -100 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        // if(matrix.empty() || matrix[0].empty()) return {};


        // vector<int> res;
        // int m = matrix.size(), n = matrix[0].size();
        // int up = 0, down = m-1, left = 0, right = n-1;


        // while(true){
        //     //从左到右
        //     for(int i = left; i <= right; i++) res.push_back(matrix[up][i]);
        //     if(++up > down) break;
        //     //从上到下
        //     for(int i = up; i <= down; i++) res.push_back(matrix[i][right]);
        //     if(--right < left) break;
        //     //从右到左
        //     for(int i = right; i >= left; i--) res.push_back(matrix[down][i]);
        //     if(--down < up) break;
        //     //从下到上
        //     for(int i = down; i >= up; i--) res.push_back(matrix[i][left]);
        //     if(++left > right) break;
        // }
        // return res;



        if(matrix.empty() || matrix[0].empty()) return {};

        int m = matrix.size(), n = matrix[0].size();

        vector<int> res;

        int up = 0, down = m-1, left = 0, right = n-1;

        while(true){
            //从左到右
            for(int i = left; i <= right; i++) res.push_back(matrix[up][i]);
            if(++up > down) break;
            //从上到下
            for(int i = up; i <= down; i++) res.push_back(matrix[i][right]);
            if(--right < left) break;
            //从右到左
            for(int i = right; i >= left; i--) res.push_back(matrix[down][i]);
            if(--down < up) break;
            //从下到上
            for(int i =  down; i >= up; i--) res.push_back(matrix[i][left]);
            if(++left > right) break;
        }
        return res;



    }
};
// @lc code=end

